/**
 * @file big_integer.hpp
 * @putpose define uinteger class
 */

#ifndef __BIG_INTEGER_HPP__
#define __BIG_INTEGER_HPP__

#include "big_numbers.hpp"
#include "integer_traits.hpp"

#include <vector>

BIG_NUMBERS_NAMESPACE_BEGIN

/**
 * @section Overview
 *  Class uinteger provides arbitrary precision arithmetic operations
 *  for unsigned integers.
 *  uinteger is designed to be abstracted from
 *   - numbers base
 *   - digit type, in which a single digit can be stored
 *   - double digit type, which can be used to do arithmetic on single digits
 *     without overflows
 *   - character type that is used to do base 10 conversions to/from strings
 *   - the container that provides a storage for holding digits and a forward
 *     iterator facility to iterate over digits
 *   - a vector-like container, which is supposed to be a "faster" container
 *     for digits, supporting resize operation
 *
 *  uinteger can be created by providing a digit, an unsigned integer, a string
 *  of characters or another uinteger.
 *
 * @note Different base_type containers can be used in different situations, supposedly
 *  based on memory conditions. std::vector should be fine on most cases, but if
 *  the memory is too fragmented and is small, std::list/deque may be better choices.
 *
 * @note The first digit of a uinteger is always non-zero.
 *
 * @section Current restrictions
 *  only decimal string conversions is supported (the traits::to/from_char are
 *  supposed to be aware of this fact.
 *
 * @section to-do enhancements
 *  support base-to-base conversions
 *  support more generic way for char-string <-> digit conversions
 *  optimize division's q's determination by not using uinteger
 */

template <typename traits>
class uinteger: private traits::base_type
{
public:
        typedef typename traits::base_type base_type;
        typedef typename traits::digit digit;
        typedef typename traits::double_digit double_digit;

        typedef typename traits::digits digits;

        typedef typename traits::char_type char_type;
        typedef typename traits::base_type::size_type size_type;
        typedef typename traits::string string;

        typedef typename base_type::iterator iterator;
        typedef typename base_type::const_iterator const_iterator;
        typedef typename base_type::reverse_iterator reverse_iterator;
        typedef typename base_type::const_reverse_iterator const_reverse_iterator;

public:
        /// @name Constructors (we are OK with the default copy-ctor)
        /// default constructor, creates the integer zero
        uinteger();

        /// from int constructor
        explicit uinteger(unsigned int);

        ///  from digit constructor (thus we prevent unsigned int to be the digit_type)
        explicit uinteger(digit);

        /// from string constructor
        explicit uinteger(const string&);

        /// from a sequence of digits constructor
        explicit uinteger(const digits&);
        /// @}

        /// @name Various assignment operators @{
        uinteger& operator=(unsigned int);
        uinteger& operator=(digit);
        uinteger& operator=(const string&);
        uinteger& operator=(const digits&);
        /// @}

        /// @name Unary operators @{
public:
        uinteger& operator ++(); // prefix
        uinteger operator ++(int); // postfix
        uinteger& operator --(); // prefix
        uinteger operator --(int); // postfix
        /// @}

        /// @name Arithmetic assignments @{
public:
        uinteger& operator += (const uinteger&);
        uinteger& operator -= (const uinteger&);
        uinteger& operator *= (const uinteger&);
        uinteger& operator *= (digit);
        uinteger& operator /= (const uinteger&);
        uinteger& operator /= (digit);
        uinteger& operator %= (const uinteger&);
        uinteger& operator %= (digit);
        /// @}

        /// @name Arithmetic operators @{
public:
        uinteger operator +(const uinteger&) const;
        uinteger operator -(const uinteger&) const;
        uinteger operator *(const uinteger&) const;
        uinteger operator *(digit) const;
        uinteger operator /(const uinteger&) const;
        uinteger operator /(digit) const;
        uinteger operator %(const uinteger&) const;
        digit operator %(digit) const;
        /// @}

        /// @name Relational operations @{
public:
        bool operator <(const uinteger&) const;
        bool operator >(const uinteger&) const;
        bool operator ==(const uinteger&) const;
        bool operator !=(const uinteger&) const;
        bool operator <=(const uinteger&) const;
        bool operator >=(const uinteger&) const;
        /// @}

        /// @name Convenience operations @{
public:
        /**
         *  @brief divmod's divides computes *this / d -> div
         *  @return *this % d
         */
        uinteger divmod(uinteger d, uinteger& div) const;
        digit divmod(digit, uinteger& div) const;

        /**
         *  @brief modexp computes modular exponentiation
         *  @return (*this ^ exp) % mod
         */
        uinteger modexp(const uinteger& exp, const uinteger& mod) const;

        /**
         *  @return true, if *this is just one digit; false - otherwise
         */
        bool is_digit() const;

        /**
         *  @return true, if *this % 2 == 1
         */
        bool is_odd() const;

        /**
         *  @return a random uinteger, decimal representation of which is of @a size digits
         */
        static uinteger decimal_rand(size_type size);

        /**
         *  @brief a specialized operation to exchange values stored in two uintegers
         */
        void swap(uinteger&);
        /// @}

        /// @name Conversions @{
public:
        void to_string(string&) const;
        void from_string(const string&);
        operator string () const;
        /// @}

        /// @name Data examination @{
public:
        const_iterator data_begin() const;
        const_iterator data_end() const;
        using base_type::clear;
        using base_type::size;
        /// @}

public:
        static const uinteger zero;
        static const uinteger one;
        static const digit max_digit = traits::max_digit;

private:
        static const double_digit end_digit = traits::end_digit;

        /// name Base type members explicit using-declarations @{
private:
        using base_type::begin;
        using base_type::end;
        using base_type::rbegin;
        using base_type::rend;
        using base_type::empty;
        using base_type::push_back;
        using base_type::front;
        using base_type::back;
        /// @}

private:
        void from_int(unsigned int);

        void normalize(); //remove the leading zeroes, if any
        bool subtract(const uinteger&); // false means underflow
        uinteger& mul(const uinteger&, const uinteger&);

        static void sub_digits(digit& d1, digit d2, digit& borrow);
        static void add_digits(digit& d1, digit d2, digit& carry);
        static digit div_digits(digit& nom, digit d);
        static digit divmod(reverse_iterator, reverse_iterator, const uinteger&);
        static digit divmod(const_reverse_iterator, const_reverse_iterator, digit, uinteger&);
        static bool subtract(iterator b, iterator e, const uinteger&); // false means underflow
        static digit add(iterator b, iterator e, const uinteger&); // returns the carry

        static bool good_digit(digit);
        bool has_invalid_digits();
        void check_invalid_digits();
        static void check_invalid_base_10_digit(char_type);
        static void check_invalid_string(const string&);
};

typedef integer_traits<unsigned short, std::vector<unsigned short>,
                         unsigned int, 10, char> integer_short_vector_10_traits;
typedef uinteger<integer_short_vector_10_traits> uinteger_short_vector_10;

typedef integer_traits<unsigned short, std::vector<unsigned short>,
                         unsigned int, 65536, char> integer_short_vector_ff_traits;
typedef uinteger<integer_short_vector_ff_traits> uinteger_short_vector_ff;

BIG_NUMBERS_NAMESPACE_END

#include "big_integer.tcc"

#endif // __BIG_INTEGER_HPP__
